class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n=nums.size();
        vector<int> f(n);
        vector<int> g(n);
        f[0]=nums[0];
        g[0]=nums[0];
        int ret=nums[0];
        for(int i=1;i<n;++i)
        {
            f[i]=max(nums[i],max(f[i-1]*nums[i],g[i-1]*nums[i]));
            g[i]=min(nums[i],min(g[i-1]*nums[i],f[i-1]*nums[i]));
            ret=max(ret,f[i]);
        }
        return ret;
    }
};
